/*
 * Created on May 19, 2005
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package clustering.implementations;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Random;

import clustering.framework.*;

/**
 * @author Administrator
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class DQPTreeConstructor implements IClusterTreeConstructor{
	QNode [] qNodes = null;
    int last_operation = -1;
    Hashtable htPath = new Hashtable();
    public String [] filesList = null;
       
    int [] selected_q = null;
    public Quartet getRandomQuartet(ArrayList alQuartets){
    	Random rand = new Random();
    	int index = rand.nextInt(alQuartets.size());
    	while(selected_q[index]==1){
    		index = rand.nextInt(alQuartets.size());
    	}
    	selected_q[index]=1;
    	return (Quartet)alQuartets.get(index);
    }
    public int [] generateRandomNodesList(Quartet q,int n){
    	Random rand = new Random();
    	int index = rand.nextInt(n);
    	int [] selected_t = new int[n];
    	int [] list = new int[n-4];
    	for(int i=0;i<n-4;i++){
    		while(selected_t[index]==1 || index == q.nodes[0] || index == q.nodes[1] || index == q.nodes[2] || index == q.nodes[3]){
    			index = rand.nextInt(n);
    		}
    		list[i] = index;
    		selected_t[index]=1;
    	}
    	return list;
    }
    ArrayList alEdges = null;
    double last_tree_score;

    void addNodeInBestPlace(QuartetTree qt, int node_index, double [][] dm){
    	QNode qn = getBestNode(node_index,dm);
    	TreeEdge te = new TreeEdge(qn,qn.adj[0]);
    	connectNode(qt,te,node_index,new QNode(-1,null,null,null,-1),new QNode(-1,null,null,null,-1));
    }
    
    QNode getBestNode(int node_index, double [][] dm){
    	QNode min_node = null;
    	double min_dist = Double.MAX_VALUE;
    	for(int i=0;i<node_count;i++){
    		QNode node = qNodes[i];
    		if(node.label == -1)continue;
    		if(dm[node.label][node_index] < min_dist){
    			min_dist = dm[node.label][node_index];
    			min_node = node;
    		}
    	}
    	return min_node;
    }
    void populateEdgesList(){
    	alEdges.clear();
    	for(int i=0;i<node_count;i++){
    		QNode qn = qNodes[i];
    		if(qn.label == -1){
    			for(int j=0;j<3;j++){
    				TreeEdge te = new TreeEdge(qn,qn.adj[j]);
	    			if(!containsEdge(te)){
	    				alEdges.add(te);
	    			}
    			}    			
    		}
    	}
    }
    boolean containsEdge(TreeEdge te){
    	for(int i=0;i<alEdges.size();i++){
    		TreeEdge t = (TreeEdge)alEdges.get(i);
    		if((t.q1 == te.q1 && t.q2 == te.q2)||(t.q2 == te.q1 && t.q1 == te.q2))return true;
    	}
    	return false;
    }
        
    /*
    void updatePathTable(QNode new_node, QuartetTree qt, TreeEdge te){
    	QNode [] qNodes = new QNode[node_count];
    	for(int i=0;i<node_count;i++){
    		qNodes[i] = this.qNodes[i];
    	}
    	htPath.put(new_node,qt.Dijkstra(new_node,qNodes));
    	if(htPath.size() == 1)return;
    	
    	for(int i=0;i<node_count;i++){
    		QNode qn = qNodes[i];
    		if(qn.label != -1){
    			Hashtable ht = (Hashtable)htPath.get(qn);
    			ArrayList al = qt.Dijkstra(qn,new_node,qNodes);
    			ht.put(new_node,al);
    			for(int j=0;j<node_count;j++){
    				QNode qn2 = qNodes[j];
    				if(qn2.label != -1 && qn != qn2){
    					al = (ArrayList)ht.get(qn2);
    					for(int k=1;k<al.size();k++){
    						QNode q1 = (QNode)al.get(k-1);
    						QNode q2 = (QNode)al.get(k);
    						if(q1 == te.q1 && q2 == te.q2){
    							al.add(k,new_node.adj[0]);
    						}
    						if(q2 == te.q1 && q1 == te.q2){
    							al.add(k,new_node.adj[0]);
    						}
    					}
    				}
    			}
    		}
    	}    	
    }
    */
    
    boolean treeContainsQuartet(Quartet q){
    	int count = 0;
    	for(int i=0;i<node_count;i++){
    		QNode qn = (QNode)qNodes[i];
    		if(qn.label == q.nodes[0] || qn.label == q.nodes[1] || qn.label == q.nodes[2] || qn.label == q.nodes[3])count++;
    	}
    	if(count == 4){
    		return true;
    	}
    	return false;
    }
    
    double computeTreeScore(QuartetTree qt){
    	double Ct = 0;
    	//htPath.clear();
    	double count = 0;
        for(int i=0;i<alQuartets.size();i++){
            Quartet q = (Quartet)alQuartets.get(i);
            if(treeContainsQuartet(q)){
            	if(isConsistent(q,qt)){
               		Ct += q.weight;
               		count++;
           		}
            }
        }
        return Ct;
    }
    void disconnectNode(QNode qn){
    	QNode nr = qn.adj[0];
    	QNode qn1 = nr.adj[0];
    	QNode qn2 = nr.adj[1];
    	for(int i=0;i<3;i++){
    		if(qn1.adj[i]==nr)qn1.adj[i]=qn2;
    		if(qn2.adj[i]==nr)qn2.adj[i]=qn1;
    	}
    	node_count-=2;
    	/*
    	if(htPath.get(qn) != null){
    		htPath.remove(qn);
    	}
    	for(int i=0;i<node_count;i++){
    		qn1 = qNodes[i];
    		if(qn1.label != -1){
    			for(int j=0;j<node_count;j++){
    				qn2 = qNodes[j];
    				if(qn2.label != -1 && qn2.label != qn1.label){
    					ArrayList path = (ArrayList)((Hashtable)htPath.get(qn1)).get(qn2);
    					for(int k=0;k<path.size();k++){
    						if((QNode)path.get(k)==nr){
    							path.remove(k);
    							break;
    						}
    					}
    				}
    			}
    		}
    	}
    	*/
    }
    
    void connectNode(QuartetTree qt, TreeEdge te, int node_index, QNode cn_qn, QNode cn_qr){
    	cn_qn.label = node_index;// = new QNode(node_index,null,null,null);
    	
    	cn_qr.label = -1;
    	cn_qr.adj[0] = te.q1;//= new QNode(-1,te.q1,te.q2,qn);
    	cn_qr.adj[1] = te.q2;
    	cn_qr.adj[2] = cn_qn;
    	
    	cn_qn.adj[0] = cn_qr;
    	cn_qn.adj[1] = null;
    	cn_qn.adj[2] = null;
    	for(int i=0;i<3;i++){
    		if(te.q1.adj[i]==te.q2)te.q1.adj[i]=cn_qr;
    	}
    	for(int i=0;i<3;i++){
    		if(te.q2.adj[i]==te.q1)te.q2.adj[i]=cn_qr;
    	}
    	qNodes[node_count++]=cn_qr;
    	qNodes[node_count++]=cn_qn;
    	//updatePathTable(qn,qt,te);
    	//return cn_qn;
    }
    
    ArrayList alQuartets = null;
    public ArrayList generateQuartetList(double [][] dm, Quartet q){
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < 4; i++){
          for (int j = i+1; j < 4; j++){
            for (int k = j+1; k < 4; k++){
              for (int l = k+1; l < 4; l++){
                Quartet q1 = new Quartet(q.nodes[i],q.nodes[j],q.nodes[k],q.nodes[l],dm);
                alQuartets.add(q1);
                Quartet q2 = new Quartet(q.nodes[i],q.nodes[k],q.nodes[j],q.nodes[l],dm);
                alQuartets.add(q2);
                Quartet q3 = new Quartet(q.nodes[i],q.nodes[l],q.nodes[j],q.nodes[k],dm);
                alQuartets.add(q3);
              }
            }
          }
        }
        return alQuartets;
    }
    public String ConstructXMLTree(double [][] dDistanceMatrix)throws Exception{
    	qNodes = new QNode[2*dDistanceMatrix.length - 2];
        ArrayList alBestQuartets = Quartet.generateBestQuartetList(dDistanceMatrix);
        alQuartets = Quartet.generateFullQuartetList(dDistanceMatrix);
        QuartetTree qt = null;
        selected_q = new int[alBestQuartets.size()];
        alEdges = new ArrayList();
        QNode [] best_nodes = null;
        double best_score = Double.MAX_VALUE;
        for(int i=0;i<100;i++){
        	alEdges.clear();
//        	htPath.clear();
        	qt = new QuartetTree();
        	Quartet q = null;
        	q = getRandomQuartet(alBestQuartets);
        	initializeFromQuartet(qt,q);
        	int [] nodes_list = generateRandomNodesList(q,dDistanceMatrix.length);
        	for(int j=0;j<nodes_list.length;j++){
        		addNodeInBestPlace(qt,nodes_list[j],dDistanceMatrix);
        	}
        	last_tree_score = computeTreeScore(qt);
        	if(last_tree_score < best_score){
        		best_score = last_tree_score;
        		best_nodes = this.cloneQuartetNodes(qNodes,qt);
        	}
        }
        qNodes = best_nodes;
        qt.root = this.getRandomInternNode();
        qt.St = (Quartet.worst_cost.doubleValue() - best_score)/(Quartet.worst_cost.doubleValue() - Quartet.best_cost.doubleValue());
        return qt.toString();
    }
    /*
    boolean equalTrees(QNode [] old_list, QNode [] new_list){
    	int i1, i2;
    	for(int i=0;i<old_list.length;i++){
    		i1 = getNodeIndex(old_list[i],old_list);
    		i2 = getNodeIndex(new_list[i],new_list);
    		if(i1 != i2)return false;
    		for(int j=0;j<old_list[i].adj.length;j++){
    			i1 = getNodeIndex(old_list[i].adj[j],old_list);
    			i2 = getNodeIndex(new_list[i].adj[j],new_list);
    			if(i1 != i2)return false;
    		}
    	}
    	return true;
    }
    */
    int getNodeIndex(QNode qn, QNode [] nodesList){
    	for(int i=0;i<nodesList.length;i++){
    		if(nodesList[i]==qn)return i;
    	}
    	return -1;
    }
    
    QNode [] cloneQuartetNodes(QNode [] listNodes, QuartetTree qt){
    	QNode [] newNodes = new QNode[listNodes.length];
    	for(int i=0;i<newNodes.length;i++)newNodes[i] = new QNode(-1,null,null,null,-1);
    	for(int i=0;i<listNodes.length;i++){
    		newNodes[i].label = listNodes[i].label;
    		for(int j=0;j<newNodes[i].adj.length;j++){
    		    int index = getNodeIndex(listNodes[i].adj[j],listNodes);
    		    if(index != -1)newNodes[i].adj[j] = newNodes[index];
    		}
    	}
    	qt.root = getRandomInternNode();
    	return newNodes;
    }
    
    boolean isConsistent(Quartet q, QuartetTree qt){
    	QNode [] qNodes = new QNode[node_count];
    	for(int i=0;i<node_count;i++){
    		qNodes[i] = this.qNodes[i];
    	}
        
    	QNode a = getNodeByLabel(q.nodes[0]);
        QNode b = getNodeByLabel(q.nodes[1]);
        QNode c = getNodeByLabel(q.nodes[2]);
        QNode d = getNodeByLabel(q.nodes[3]);
        
        if(a==null || b==null || c==null || d==null)return false;
        
        if(htPath.get(a)==null){
        	htPath.put(a,qt.Dijkstra(a,qNodes));
        }        
        if(htPath.get(b)==null){
        	htPath.put(b,qt.Dijkstra(b,qNodes));
        }        
        if(htPath.get(c)==null){
        	htPath.put(c,qt.Dijkstra(c,qNodes));
        }        
        if(htPath.get(d)==null){
        	htPath.put(d,qt.Dijkstra(d,qNodes));
        }        
        ArrayList path1 = (ArrayList)((Hashtable)htPath.get(a)).get(b);
        ArrayList path2 = (ArrayList)((Hashtable)htPath.get(c)).get(d);
        
        for(int i=1;i<path1.size()-1;i++){
            QNode qn1 = (QNode)path1.get(i);
            for(int j=1;j<path2.size()-1;j++){
                QNode qn2 = (QNode)path2.get(j);
                if(qn1 == qn2)return false;
            }
        }
        return true;
    }
    QNode getNodeByLabel(int label){
        for(int i=0;i<node_count;i++){
            QNode qn = qNodes[i];
            if(qn.label == label)return qn;
        }
        return null;
    }

    /*
    void performRandomMutation(QuartetTree qt){
    	int operation = rand.nextInt(3);
        last_operation = operation;
        QNode n1 = null, n2 = null;
        if(operation == 0 || operation == 1){
        	if(operation == 0){ // leaf swap
        	    n1 = getRandomLeafNode();
        	    n2 = getRandomLeafNode();
        		while(n1.adj[0] == n2.adj[0]){
        			n1 = getRandomLeafNode();
        			n2 = getRandomLeafNode();
        		}
        		// just exchange their labels
        		int temp_label = n1.label;
        		n1.label = n2.label;
        		n2.label = temp_label;
            }else{ // subtree swap
                n1 = getRandomInternNode();
                n2 = getRandomInternNode();
        	    ArrayList path = qt.Dijkstra(n2,n1,qNodes);
        	    
        	    // make sure the path has more than 3 nodes, including n1 and n2
                while(path.size() <= 3){
                	n1 = getRandomInternNode();
                	n2 = getRandomInternNode();
                	path = qt.Dijkstra(n2,n1,qNodes);
            	}

                // exchange the adjacent nodes
                QNode bucket = n1.adj[n1.getAdjIndex((QNode)path.get(1))];
                n1.adj[n1.getAdjIndex((QNode)path.get(1))] = n2.adj[n2.getAdjIndex((QNode)path.get(path.size()-2))];
                n2.adj[n2.getAdjIndex((QNode)path.get(path.size()-2))] = bucket;
                
                // update their referers
                QNode n1_adj = (QNode)path.get(1);
                n1_adj.adj[n1_adj.getAdjIndex(n1)] = n2;
                QNode n2_adj = (QNode)path.get(path.size()-2);
                n2_adj.adj[n2_adj.getAdjIndex(n2)] = n1;
            }        	        	
        }else{ // subtree transfer
            n1 = getRandomNode();
            n2 = getRandomNode();
            ArrayList path = qt.Dijkstra(n2,n1,qNodes);
            
        	while(path.size() <= 3){
        	    n1 = getRandomNode();
                n2 = getRandomNode();
                path = qt.Dijkstra(n2,n1,qNodes);
    		}
        	
        	// --- begin of disconnect ---
        	// the node to be transfered
        	QNode tn = (QNode)path.get(path.size()-2);
        	// this is the next node after tn from the path from n2 to n1
        	QNode n3 = (QNode)path.get(path.size() - 3);
        	// the node to be shifted
        	QNode shift = tn.adj[tn.getThirdAdjIndex(n3,n2)];
        	
        	n3.adj[n3.getAdjIndex(tn)] = shift;
        	shift.adj[shift.getAdjIndex(tn)] = n3;
        	// --- end of disconnect ---
        	
        	// --- begin of connect ---
        	QNode n4 = (QNode)path.get(1);
        	n1.adj[n1.getAdjIndex(n4)] = tn;
        	
        	int i1 = rand.nextInt(2);
        	int i2 = (i1 + 1)%3;
        	int i3 = (i2 + 1)%3;
        	
        	tn.adj[i1] = n1;
        	tn.adj[i2] = n2;
        	n4.adj[n4.getAdjIndex(n1)] = tn;
        	tn.adj[i3] = n4;
        	// --- end of connect --
        	
        }
	}
    */
	Random rand = new Random();
    QNode getRandomNode(){
        int k = rand.nextInt(qNodes.length);
        return qNodes[k];
    }
    QNode getRandomLeafNode(){
        QNode qn = getRandomNode();
        while(qn.label == -1)qn = getRandomNode();
        return qn;
    }
    QNode getRandomInternNode(){
        QNode qn = getRandomNode();
        while(qn.label != -1)qn = getRandomNode();
        return qn;
    }
    
    // creates the initial quartet tree
    /*
    QuartetTree createInitialTree(int n){
        QuartetTree qt = new QuartetTree();
        node_count = 0;
        for(int i=0;i<3;i++)qt.root.adj[i] = new QNode(-1,qt.root,null,null);
        addNodePair(qt.root.adj[0],0,n/3);
        addNodePair(qt.root.adj[1],n/3,2*n/3);
        addNodePair(qt.root.adj[2],2*n/3,n);
        qNodes[node_count] = qt.root;
        qt.N = n;
        return qt;
    }
    */
    public void initializeFromQuartet(QuartetTree qt, Quartet q){
    	node_count = 0;
    	qNodes[node_count++] = qt.root;
    	qt.root.adj[0] = new QNode(-1,qt.root,null,null,-1);
    	qNodes[node_count++] = qt.root.adj[0];
    	
    	qt.root.adj[1] = new QNode(q.nodes[0],qt.root,null,null,-1);
    	qNodes[node_count++] = qt.root.adj[1];
    	
    	qt.root.adj[2] = new QNode(q.nodes[1],qt.root,null,null,-1);
    	qNodes[node_count++] = qt.root.adj[2];
    	
    	qt.root.adj[0].adj[1] = new QNode(q.nodes[2],qt.root.adj[0],null,null,-1);
    	qNodes[node_count++] = qt.root.adj[0].adj[1];
    	
    	qt.root.adj[0].adj[2] = new QNode(q.nodes[3],qt.root.adj[0],null,null,-1);
    	qNodes[node_count++] = qt.root.adj[0].adj[2];
    }
    
    // counter for the number of nodes to be added in the list of nodes
    int node_count = 0;
    
    // creates new nodes for second - qn.adj[1] - and third neighbor - qn.adj[2]
    // the first neighbor - qn.adj[0] - is the link to the referer node
    /*
    void addNodePair(QNode qn, int k, int n){
        qNodes[node_count++] = qn;
        if(k >= n)return;
        
        qn.adj[1] = new QNode(k,qn,null,null);
        qNodes[node_count++] = qn.adj[1];
        if(n - k >= 3){
            qn.adj[2] = new QNode(-1,qn,null,null);
            addNodePair(qn.adj[2],k+1,n);
        }else{
            qn.adj[2] = new QNode(k+1,qn,null,null);
            addNodePair(qn.adj[2],k+2,n);
        }       
    }
    */
}